package offer;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class offerII_0087 {
    public List<String> restoreIpAddresses(String s) {
        List<String> result=new LinkedList<>();
        List<Integer> path=new ArrayList<>();
        search(result,path,s,0);
        return result;
    }
    public void search(List<String> result,List<Integer> path,String s,int index){
        if(index>=s.length()&&path.size()<4) return;
        if(path.size()==4&&index<s.length()) return;
        if(index>=s.length()&&path.size()==4){
            String tmp="";
            for(int i=0;i<3;++i){
                tmp+=path.get(i);
                tmp+=".";

            }
            tmp+=path.get(3);
            result.add(tmp);
            return;
        }
        int num=0;
        if(s.charAt(index)=='0'){
            path.add(0);
            search(result, path, s, index+1);
            path.remove(path.size()-1);
            return;
        }
        for(int i=index;i<s.length()&&i<index+3;++i){
            num=10*num+(s.charAt(i)-'0');
            if(num>255) break;
            path.add(num);
            search(result, path, s, i+1);
            path.remove(path.size()-1);
        }
    }
}
